1. Field of the Invention
The present invention relates generally to networking and communications.
2. Description of the Background Art
Computer networks are widely used to provide increased computing power, sharing of resources and communication between users. Networks may include a number of computer devices within a room, building or site that are connected by a high-speed local data link such as Ethernet, token ring, or the like. Local area networks (LANs) in different locations may be interconnected to form a wide area network (WAN).
The Internet is an interconnected set of networks, wherein each of the constituent networks retains its identity, and special mechanisms are needed for communication across multiple networks. The constituent networks are referred to as subnetworks.
Each subnetwork in the Internet supports communication among the devices connected to that subnetwork. Further, subnetworks are connected by devices referred to as interworking units (IWUs). A particular IWU is a router, which is used to connect two networks that may or may not be similar. The router employs internet protocol (IP) to allow communication between hosts and routers through the routers present in the internet protocol network. IP provides a connectionless or datagram service between stations.
Routers are specialized computing devices that route digital packets between subnets across the internet or within an intranet. Routers receive packets from one location (e.g., source computer or another router) and forward them to the next destination (e.g., destination computer or another router) over the most efficient available path.
Routers generally use routing tables to direct packet traffic over a network. Routing tables have multiple entries, or routes, each route routes to a single subnet. A subnet is identified by it's network address and it's width or network mask. Each route specifies forwarding information for the set of hosts that fall within that route's subnet. Each subnet may be further divided into smaller subnets. These subnets may be routed to using routes specific to the subdivided subnets, or there may be just one route that is used to route to a set of subnets contained within a larger subnet. Each subnet can be uniquely identified by the network part of it's network address and it's network mask.
Contiguous network routes are routes such that the mask of the subnet for the route must (when represented in binary) consist of a contiguous string of ‘1’s followed by a contiguous string of ‘0’s. The total number of bits for IPv4 will be less than 32.
Routes may be described using a notation [D,W], where D represents the network address and W represents the width which is the number of ones in the route's contiguous mask. For purposes of discussion, it may be assumed that a particular pair of values [D,W] uniquely identifies a route. However this is not a requirement for internet routers, nor is it a requirement for this invention. There may be multiple routes in the routing information base, RIB, that share a particular pair of values [D,W].
Two routes R1=[D1,W1] and R2=[D2,W2] are defined to be equivalent if (W1==W2)&&((D1 & WIDTH_TO_MASK(W1))==(D2 & WIDTH_TO_MASK(W2)). A route R3 is defined to be a subset of a route R4 if (W3>W4)&&((D3 & WIDTH_TO_MASK(D4))==(D4 & WIDTH_TO_MASK(D4)). If a route R2 is a subset of a route R1 then it may be said that R1 contains route R2. WIDTH_TO_MASK(W) is a function that translates a number, W, from 0 to 32 into a network mask with W 1's. Here, we define the operators ‘&&’=logical and, ‘&’=bitwise and, ‘==’ equality, ‘>’=greater than.
For instance, in the Internet context, each entry consists of the 32-bit network (Internet Protocol) address such as “192.56.7.48” and a width, or prefix length, such as 8, 16, or 24 (these are not exclusive, the width may be any number from 0 to the number of bits in the address.) The width specifies how many bits a router should consider when comparing a destination to a route for the purpose of determining if that IP address falls within (or “matches” or “is contained by”) the route. For instance, if the route has a network address of “192.56.7.48” and a width of “16”, the router need only consider the first two bytes to determine if a particular IP address matches the route (in other words, falls within the subnet specified for the route) and may effectively read the network address as “192.56.0.0”.
Associated with each entry in the routing table is forwarding information. In some implementations, the forwarding information may comprise a “next hop” value that indexes into a second table. The second or “next hop” table is used to map layer 3 addresses to layer 2 forwarding information of adjacent routers and hosts. For instance, the IP address “192.56.7.48/16” may have an associated next hop value of “17”, meaning that the IP address and the layer 2 forwarding information for either the next hop router or for the host itself if the host is directly connected is at location 17 in the next hop table.
The router uses the routing table to select the path to use when routing a packet through the network. When a packet arrives at a router, the router first finds the route in the routing table that provides the best match to the destination address. Many routing systems use best match prefix for route selection. This rule dictates that the route that best matches the destination of a packet is the route to use for routing the packet. Using best match prefix, the route that “best” matches the packet is the route with the longest prefix and whose subnet contains the destination address. Packets are forwarded using the forwarding information associated with the route that best matches the destination address from the packet. There are many different high-speed algorithms to quickly look up addresses in the routing tables.
Due to the explosive growth of content being made available on the World Wide Web, the Internet is rapidly growing to fill every corner of the world. The demands of the Internet backbone routers are commensurately increasing. Nodes are being added to the network at an extremely fast rate. It is estimated that the number of routes in the Internet backbone has been growing by 10,000 routes per year. More sophisticated and faster routers are being developed, with larger routing tables, to accommodate the increasing number of routes.
Since IP routing lookups have been inherently slow and complex, operations with prior art solutions have led to a proliferation of techniques to optimize them, one method has been to avoid performing route lookups when possible. For example, current IP router designs may use caching techniques wherein each entry in the cache corresponds to a single recently used destination address, along with the associated forwarding information that should be used to forward traffic to that destination. The technique relies on there being enough temporal locality in the traffic so that the cache hit rate is sufficiently high and the cost of a routing lookup is amortized over several packets. These caching methods may have worked somewhat well in the past. However, as the current rapid growth of the Internet increases the required size and the computation overhead of programming hardware caches of this nature may become uneconomical.
It is highly desirable to improve technology for networking and communications. In particular, it is desirable to improve routers and network routing caches.